In a digital communication system, the received data may have been corrupted by noise and distortion. In consequence, the digital data obtained at the receiving station is not an accurate replica of the data transmitted. Such errors may be reduced by encoding the transmitted data to add redundancy to the data before transmission.
Redundancy may introduced by increasing the symbol rate. For example, error checking and error correcting codes may be appended to fixed-length blocks of source data, and the combination may then sent at a higher data rate. The resulting increase in bandwidth, however, subjects the receiver to additional noise.
Alternatively, signal-space codes may be used to add redundancy by converting the source data into a "line code" which may be sent at the same symbol rate but which uses an enlarged number of possible symbols (discrete points within the signal space). The bandwidth required by such codes is no larger than that of an equivalent uncoded system, so there is no increase in noise at the receiver. However, because the symbols must be more closely spaced to avoid an increase in transmitted power, noise immunity is reduced. In transmission systems having a limited, fixed bandwidth, such as voice-grade telephone links, signal-space coding permits significantly higher rates of error-corrected transmission to be realized.
One class of signal-space code which has enjoyed widespread acceptance because of its superior performance is the "trellis code," a convolutional code best explained using a trellis diagram. In the trellis diagram, vertical columns of nodes represent the possible states which can be assumed at successive points in time by a "state machine" which encodes the source data. Before transmission begins, the encoding machine is initialized to a predetermined state. Thereafter, each transmitted symbol specifies a transition from the current state to a limited number of permissible successor states. Thus, the sequence of symbols previously transmitted specifies the current state of the encoding machine. The current state in turn specifies which symbols out of the entire alphabet may validly appear next in the transmitted sequence. Thus, only selected sequences of transmitted symbols are permitted by the coding scheme, and these legitimate sequences may be represented by paths through the trellis diagram.
Each transmitted symbol accordingly represents not only a source codeword but also contains historical information, reflected in the state information which can be derived from the received sequence of symbols. This redundancy permits the transmitted symbol sequence to be accurately reconstructed even though noise and distortion have altered the message-bearing signal during transmission.
Trellis coding is used to particular advantage in the implementation of voiceband data modems of the type used to provide higher error-free data rates over dialup and leased-line analog telephone facilities. A trellis coding scheme described by Lee-Fang Wei in the IEEE Transactions on Information Theory, Vol. IT-33, No. 4, pp. 483-501 (July, 1983) is used to implement the CCITT V.32 standard which is widely used to provide modem data communications at 9600 baud. The V.32 standard uses a 32 point constellation within the signal space and an 8-state trellis encoder.
As described by Wei, significant improvements in coding gain may be realized with a more elaborate, more closely-spaced constellation of points in the signal space encoded by a state machine having a greater number of states. As explained by Wei, the 8-state trellis coding scheme used in the V.32 standard yields a coding gain of 4.01 db, whereas a 64-state, 4 dimensional coding scheme would provide a coding gain of 6.05 db. Unfortunately, a significantly larger computational burden is placed on the decoder to achieve this improvement. Using Wei's comparison, the 64-state, 4 dimensional code places sixteen times the computational burden on the decoding processor than does the simpler V.32 code.
Both the simpler and the more elaborate code structures may be processed using the same basic decoding method: the highly efficient Viterbi algorithm, named after its originator A. J. Viterbi, and described in the IEEE Transactions on Information Theory, Vol. IT-13, pp. 260-269 (April 1967). Nonetheless, the larger number of computational steps required to perform 64-state 4-dimensional Viterbi decoding has severely limited the extent to this larger trellis structure has been used to implement commercially practical communication systems.